Several recent stochastic parsers use bilexical grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present O(n^4) parsing algorithms for two bilexical formalisms, improving the prior upper bounds of O(n^5). For a common special case that was known to allow O(n^3) parsing (Eisner, 1997), we present an O(n^3) algorithm with an improved grammar constant.
展开▼
